package com.platform.modules.alg.alglib.poj1741;

import java.util.Arrays;

public class Poj1741 {
    private int maxn = 10005;
    int cnt, n, k, ans;
    int head[] = new int[maxn];
    int root, S;
    int size[] = new int[maxn];
    int f[] = new int[maxn];
    int d[] = new int[maxn];
    int dep[] = new int[maxn];
    boolean vis[] = new boolean[maxn];
    edge edge[] = new edge[maxn * 2];
    public String output = "";

    public Poj1741() {
        for (int i = 0; i < edge.length; i++) {
            edge[i] = new edge();
        }
    }

    // 获取重心
    void getroot(int u, int fa) {
        size[u] = 1;
        f[u] = 0; // 删除 u 后，最大子树的大小
        for (int i = head[u]; i > 0; i = edge[i].next) {
            int v = edge[i].to;
            if (v != fa && !vis[v]) {
                getroot(v, u);
                size[u] += size[v];
                f[u] = Math.max(f[u], size[v]);
            }
        }
        f[u] = Math.max(f[u], S - size[u]); // S为当前子树总结点数
        if (f[u] < f[root])
            root = u;
    }

    // 获取距离
    void getdep(int u, int fa) {
        dep[++dep[0]] = d[u]; // 保存距离数组
        for (int i = head[u]; i > 0; i = edge[i].next) {
            int v = edge[i].to;
            if (v != fa && !vis[v]) {
                d[v] = d[u] + edge[i].w;
                getdep(v, u);
            }
        }
    }

    // 获取 u 的子树中满足个数
    int getsum(int u, int dis) {
        d[u] = dis;
        dep[0] = 0;
        getdep(u, 0);

        Arrays.sort(dep, 1, 1 + dep[0]);
        int L = 1, R = dep[0], sum = 0;
        while (L < R)
            if (dep[L] + dep[R] <= k) {
                sum += R - L;
                L++;
            } else
                R--;
        return sum;
    }

    // 获取答案
    void solve(int u) {
        vis[u] = true;
        ans += getsum(u, 0);
        for (int i = head[u]; i > 0; i = edge[i].next) {
            int v = edge[i].to;
            if (!vis[v]) {
                ans -= getsum(v, edge[i].w);//减去重复
                root = 0;
                S = size[v];
                getroot(v, u);
                solve(root);
            }
        }
    }

    void add(int u, int v, int w) {
        edge[++cnt].to = v;
        edge[cnt].w = w;
        edge[cnt].next = head[u];
        head[u] = cnt;
    }

    public String cal(String input) {
        f[0] = 0x7fffffff; // 初始化树根
        String[] line = input.split("\n");
        String[] num = line[0].split(" ");
        n = Integer.parseInt(num[0]);
        k = Integer.parseInt(num[1]);

        cnt = 0;
        ans = 0;
        for (int i = 1; i <= n - 1; i++) {
            String[] edge = line[i].split(" ");
            int x, y, z;
            x = Integer.parseInt(edge[0]);
            y = Integer.parseInt(edge[1]);
            z = Integer.parseInt(edge[2]);
            add(x, y, z);
            add(y, x, z);
        }
        root = 0;
        S = n;
        getroot(1, 0);
        solve(root);
        output = ans + "";
        return output;
    }
}

class edge {
    int to, next, w;
}
